In a recent paper (G. D. Forney, Jr. "Coset Codes II: Binary Lattices and Related Codes," IEEE Trans. On Information Theory, Vol. 34, No. 5, Sept. 1988, pages 1152-1187) Forney introduced an algebraic derivation of trellis diagrams for block codes. The trellis diagrams obtained in the Forney disclosure have a minimum number of states, and when used in conjunction with the Viterbi algorithm, provide efficient methods for maximum-likelihood (ML) soft-decision decoding of block codes. Computational efforts of a Viterbi algorithm decoder include branch metric calculations, Add/Compare/Select (ACS) operations, and trace back. The complexity of branch metric calculations can be minimized by using a basis for the generator matrix of the code such that fast transform techniques (e.g., the fast Hadamard transform), become applicable (See the above-mentioned Forney article, as well as S. P. Adoul, "Fast ML Decoding Algorithm for the Nordstrom Robinson Code," IEEE Trans. On Information Theory, Vol. IT-33, No. 6, Nov. 1987, pp. 931-33; and Y. D. Karyakin, "Fast Correlation Decoding of Reed-Muller Codes," Problems of Information Transmission, Vol. 23, No. 3, 1987, pp. 121-129.) For many codes, including the Golay code, with a large number of trellis states, the complexity of the ML decoder is dominated by the number of computations required for ACS operations. The prior art decoding schemes, thus, involve a high degree of complexity.
In a recent publication (F. Hemmati, "Closest Coset Decoding," ICC '88 Conf. Rec., June 1988), an efficient suboptimum method was disclosed by the present inventor for soft decision decoding of block codes. In closest coset decoding, the considered code is partitioned into a subcode and its cosets and, for a received block of channel symbols, R, first the decoder finds the coset which is closest to R. Next, the decoder decodes R in that coset. Computational complexity of the closest coset algorithm is less than the computational effort of the coset decoding method (see J. H. Conway and N. J. A. Sloane, "Soft-Decision Techniques for Codes and Lattices, Including the Golay Code and the Leech Lattice" IEEE Trans. On Information Theory, Vol. IT-32, No. 1, Jan. 1986, pp. 41-50), in which R is decoded in every coset.